#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

//可以通过，速度很慢
class Solution {
public:
  bool canJump(vector<int> &nums) {
    if (nums.size() <= 1) {
      return true;
    }
    priority_queue<int, vector<int>, greater<int>> temp;
    for (int i = nums.size() - 2; i >= 0; --i) {
      if (i + nums[i] >= nums.size() - 1) {
        temp.push(i);
      } else {
        if (!temp.empty()) {
          if (i + nums[i] >= temp.top()) {
            temp.push(i);
          }
        }
      }
    }
    if ((!temp.empty()) && (temp.top() == 0)) {
      return true;
    }
    return false;
  }
};

int main(int argc, char *argv[]) {
  vector<int> a = {2, 3, 1, 1, 4};
  Solution b;
  cout << b.canJump(a) << endl;
  return 0;
}
